package com.fosss.linkedList;

import java.util.Stack;

/**
 * 单向链表
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
/*        SingleLinkedList singleLinkedList=new SingleLinkedList();
        //在链表尾添加英雄
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);

        //按编号添加英雄
        singleLinkedList.addByNode(hero4);
        singleLinkedList.addByNode(hero1);
        singleLinkedList.addByNode(hero3);
        singleLinkedList.addByNode(hero2);
//        singleLinkedList.addByNode(hero2);
        System.out.println("修改前的链表:");
        singleLinkedList.list();
        System.out.println("---------------------------------------------------");


        HeroNode heroNode=new HeroNode(1,"小松江","思思");
        singleLinkedList.update(heroNode);
        System.out.println("修改后的链表:");
        singleLinkedList.list();
        System.out.println("---------------------------------------------------");


        singleLinkedList.remove(1);
        System.out.println("删除后的链表：");
        singleLinkedList.list();

        System.out.println("除头节点外节点的个数："+getNum(singleLinkedList.getHead()));
        System.out.println("---------------------------------------------------");

        System.out.println("倒数第k个节点的数据");
        System.out.println(getNode(singleLinkedList.getHead(),3));
        System.out.println("---------------------------------------------------");

        *//**
         * 测试链表反转
         *//*
        System.out.println("反转后的链表");
        reverseList(singleLinkedList.getHead());
        singleLinkedList.list();
        System.out.println("------------------------------------------------------");

        *//**
         * 测试逆序打印
         *//*
        System.out.println("逆序打印");
        reversePrint(singleLinkedList.getHead());
        System.out.println("------------------------------------------------------");*/

        //测试合并单链表  TODO
//        SingleLinkedList list1=new SingleLinkedList();
//        list1.addByNode(hero3);
//        list1.addByNode(hero1);
//        SingleLinkedList list2=new SingleLinkedList();
//        list2.addByNode(hero4);
//
//        togetherTwo(list1,list2);


    }

    //求除了头节点以外有多少节点
    public static int getNum(HeroNode head){
        if(head.next==null){
            System.out.println("空链表");
            return 0;
        }
        int num=0;
        HeroNode p=head.next;
        while (p!=null){
            num++;
            p = p.next;
        }
        return num;
    }

    //返回倒数第k个结点数据
    public static HeroNode getNode(HeroNode head,int k){
        if(head.next == null){
            System.out.println("空链表");
            return null;
        }
        //获取一共有多少个结点
        int num = getNum(head);
        //判断k是否合法
        if(k<0||num-k<0){
            System.out.println("index不合法");
            return null;
        }
        HeroNode p=head.next;
        for(int i = 0;i<num-k; i++){
            p = p.next;
        }
        return p;
    }

    //将单链表反转
    public static void reverseList(HeroNode head){
        if(head.next == null||head.next.next==null){//如果链表为空或者只有一个节点，则直接返回
            return;
        }
        //定义一个可移动的辅助指针（变量）
        HeroNode node=head.next;
        //定义node的下一个结点，将node的下一个节点先储存起来
        HeroNode next=null;
        //定义一个新的头节点，遍历旧链表，挨个将结点插入到新链表的头节点的下一位
        HeroNode reverseNode=new HeroNode();
        //遍历
        while (node != null){
            next=node.next;
            node.next=reverseNode.next;
            reverseNode.next=node;
            node=next;//node移动到下一位
        }
        //最后将头节点指向新链表头结点的下一位
        head.next=reverseNode.next;
    }

    //利用栈这个数据结构，先进后出的特点，实现链表的逆序打印
    public static void reversePrint(HeroNode head){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        Stack<HeroNode> stack=new Stack<>();
        HeroNode cur=head.next;
        //将链表数据压入栈中
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        //遍历出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

    //合并两个有序的单链表，合并之后的链表依然有序 TODO 不会做
    public static void togetherTwo(SingleLinkedList list1,SingleLinkedList list2){
//        SingleLinkedList singleLinkedList=new SingleLinkedList();
//        HeroNode head1 = list1.getHead();
//        while(head1.next!=null){
//            singleLinkedList.addByNode(head1.next);
//            head1=head1.next;
//        }
//        HeroNode head2 = list2.getHead();
//        while(head2.next!=null){
//            singleLinkedList.addByNode(head2.next);
//            head2=head2.next;
//        }
//
//        singleLinkedList.list();
    }
}

//定义单链表类
class SingleLinkedList {
    //定义链表头
    HeroNode head = new HeroNode();

    public HeroNode getHead() {
        return head;
    }

    //向链表尾部添加数据
    public void add(HeroNode heroNode) {
        //因为head不能动，所以需要再定义一个来移动
        HeroNode temp = head;
        //遍历找到链表的尾部
        while (true) {
            //找到表尾即next为空时，退出循环
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //到达链表尾，进行添加操作
        temp.next = heroNode;
    }

    //按编号添加英雄
    public void addByNode(HeroNode heroNode){
        //同样head不能动，所以通过一个辅助变量来进行遍历
        HeroNode temp = head;
        boolean flag=false;//标志是否要添加

        while (true) {
            //没有比要添加的英雄编号大的英雄
            if(temp.next == null){
                break;
            }

            //添加到temp后边
            if(temp.next.no>heroNode.no){
                break;
            }
            else if(temp.next.no==heroNode.no){
                //链表中已经有该数据，不能添加
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag) {
            System.out.printf("要添加的英雄%s已经存在，不能重复添加\n",heroNode.name);
        }else {
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }

    //修改
    public void update(HeroNode heroNode){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp=head.next;
        boolean flag = false;
        while (true) {
            if(temp==null){//没有找到
                break;
            }
            if(temp.no==heroNode.no){
                flag = true;
                break;
            }
            temp=temp.next;
        }
        if (flag) {
            temp.name=heroNode.name;
            temp.nickname=heroNode.nickname;
        }else {
            System.out.printf("没有名为%s的英雄",heroNode.name);
        }
    }

    //删除
    public void remove(int no){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp=head;
        boolean flag = false;
        while (true) {
            if(temp.next==null){//没有找到
                break;
            }
            if(temp.next.no==no){
                flag = true;
                break;
            }
            temp=temp.next;
        }
        if (flag) {
            temp.next=temp.next.next;
        }else {
            System.out.println("没有此英雄~");
        }
    }

    //展示整个链表
    public void list() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，无法遍历");
            return;
        }
        HeroNode temp = head.next;//head不存储数据
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

//定义英雄类
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    //构造器
    public HeroNode() {
    }

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroList{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}
































